#pragma once
#include <iostream>
#include <vector>
#include <utility>

namespace me
{
	template <typename K, typename V>
	struct hashNode
	{
		hashNode(const std::pair<K, V>& val) : _data(val), _next(nullptr) {}
		std::pair<K, V> _data;
		hashNode* _next;
	};

	// ǰ������
	template <typename K, typename V, typename hash/*��keyת��Ϊ����*/>
	class hashmap;

	template <typename K, typename V, typename Ref, typename Ptr, typename hash>
	struct hashIterator
	{
		using node = hashNode<K, V>;
		using Self = hashIterator<K, V, Ref, Ptr, hash>;
		using table = hashmap<K, V, hash>;

		node* _node;
		table* _tb;

		hashIterator(node* node, table* tb):_node(node), _tb(tb) {}

		// hashmap��֧�ֵ����������++�ߵ���һ���ڵ㣬���Ϊ�գ����ҵ���һ����Ϊ�յ�Ͱ
		Self& operator++()
		{
			hash to_int;

			// ��һ���ڵ㲻Ϊ�գ�ֱ���ߵ���һ���ڵ�
			if (_node->_next) {
				_node = _node->_next;
				return *this;
			}

			// ��һ���ڵ�Ϊ�գ��ߵ���һ����Ϊ�յ�Ͱ
			// 1.���㵱ǰ����Ͱ
			size_t bucket = to_int(_node->_data.first) % _tb->_tables.size();

			// 2.�ҵ���һ����Ϊ�յ�Ͱ
			bucket++;
			while (bucket < _tb->_tables.size() && _tb->_tables[bucket] == nullptr) { bucket++; }

			// 3.�ж��Ƿ�Խ��
			if (bucket >= _tb->_tables.size()) {
				_node = nullptr;
			}
			else {
				_node = _tb->_tables[bucket];
			}
			return *this;
		}

		Ref operator*() { return _node->_data; }
		Ptr operator->() { return &_node->_data; }
		bool operator==(const Self& other)const  { return _node == other._node; }
		bool operator!=(const Self& other) const { return !(*this == other); }
	};

	template <typename K, typename V, typename hash/*��keyת��Ϊ����*/>
	class hashmap
	{
		friend hashIterator<K, V, std::pair<K, V>&, std::pair<K, V>*, hash>;
		using node = hashNode<K, V>;
		using iterator = hashIterator<K, V, std::pair<K, V>&, std::pair<K, V>*, hash>;
		using const_iterator = hashIterator<K, V, const std::pair<K, V>&, const std::pair<K, V>*, hash>;

	public:
		hashmap(const size_t n = 10)
			:_size(0)
		{
			_tables.resize(n, nullptr);
		}

		~hashmap()
		{
			// һ��һ���ڵ������
			for (auto& bucket : _tables) {
				node* cur = bucket;

				while (cur) {
					node* next = cur->_next;
					delete cur;
					cur = next;
				}
			}
		}
		
		hashmap(const hashmap& other)
			:_size(other._size)
		{
			_tables.resize(other._tables.size(), nullptr);
			for (int i = 0; i < other._tables.size(); i++) 
			{
				node* cur = other._tables[i];
				node* tail = nullptr;

				// Ͱ��Ϊ�գ�����Ͱ,β��
				while (cur) 
				{
					node* newnode = new node(cur->_data);
					if (_tables[i] == nullptr) {
						_tables[i] = newnode;
						tail = newnode;
					}
					else {
						tail->_next = newnode;
						tail = newnode;
					}
					cur = cur->_next;
				}
			}
		}

		hashmap& operator=(hashmap other)
		{
			std::swap(_tables, other._tables);
			std::swap(_size, other._size);
			return *this;
		}


		std::pair<iterator, bool> insert(const std::pair<K, V>& data)
		{
			hash to_int;

			// 1.���ж��Ƿ��Ѿ�����
			iterator is_exists = find(data.first);
			if (is_exists != end()) { return std::make_pair(is_exists, false); }

			// 2.�����������
			// ��������Ϊ1������
			if (_size >= _tables.size()) 
			{
				size_t newsize = _tables.size() == 0 ? 10 : 2 * _tables.size();
				std::vector<node*> new_t(newsize, nullptr);

				for (auto& bucket : _tables) {
					if (bucket == nullptr) continue;

					node* cur = bucket;
					while (cur) {
						node* next = cur->_next;

						// ���¹�ϣ��ӳ�䵽�±���
						size_t pos = to_int(cur->_data.first) % newsize;
						cur->_next = new_t[pos];
						new_t[pos] = cur;

						cur = next;
					}
					bucket = nullptr;
				}
				_tables.swap(new_t);
			}

			// 3.����
			size_t bucket = to_int(data.first) % _tables.size();
			node* newnode = new node(data);
			newnode->_next = _tables[bucket];
			_tables[bucket] = newnode;
			++_size;
			return std::make_pair<iterator, bool>({newnode, this}, true);
		}

		iterator find(const K& key)
		{
			if (_size == 0) return end();

			hash to_int;
			size_t bucket = to_int(key) % _tables.size();
			if (_tables[bucket] == nullptr) return end();

			node* cur = _tables[bucket];
			while (cur) {
				if (cur->_data.first == key) return { cur, this };
				cur = cur->_next;
			}
			return {nullptr, this};
		}
	
		size_t erase(const K& key)
		{
			hash to_int;
			
			size_t bucket = to_int(key) % _tables.size();
			node* cur = _tables[bucket];
			node* prev = nullptr;
			while (cur) 
			{
				if (cur->_data.first == key) 
				{
					// ͷɾ
					if (prev == nullptr) {
						_tables[bucket] = cur->_next;
					}else{
						prev->_next = cur->_next;
					}
					delete cur;
					cur = nullptr;
					--_size;
					return 1;
				}
				prev = cur;
				cur = cur->_next;
			}
			return 0;
		}

		iterator begin() 
		{
			for (auto& bucket : _tables) {
				if (bucket) return { bucket, this };
			}
			return end();
		}
		iterator end() { return { nullptr, this }; }

		const_iterator cbegin() const
		{
			for (auto& bucket : _tables) {
				if (bucket) return { bucket, this };
			}
			return cend();
		}
		const_iterator cend() { return { nullptr, this }; }

		
	private:
		std::vector<node*> _tables;
		size_t _size; // Ԫ�ظ���
	};
}